GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Constraintprogrammierung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Constraintprogrammierung</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die Constraintprogrammierung (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> Constraint Programming, CP) ist ein <a href="Programmierparadigma" title="Programmierparadigma">Programmierparadigma</a>, das seit Mitte der <a href="1980er" title="1980er">1980er</a> Jahre entwickelt wird und als Weiterentwicklung der <a href="Logische_Programmierung" title="Logische Programmierung">logischen Programmierung</a> entstanden ist. Die <a href="Constraint" title="Constraint">Constraint</a>-basierte Programmierung erlaubt die Integration von Constraints und ihren Lösungsmechanismen in eine Programmiersprache. Mittlerweile ist sie ein eigenständiger Bereich der <a href="K%C3%BCnstliche_Intelligenz" title="Künstliche Intelligenz">künstlichen Intelligenz</a> und hat vielfältige Anwendungsgebiete in Praxis und Wissenschaft.

Bei der Constraintprogrammierung beschreibt der Nutzer das Problem auf <a href="Deklarative_Programmierung" title="Deklarative Programmierung">deklarative</a> Weise, während der Lösungsprozess aus Nutzersicht in den Hintergrund tritt. Dieser wird vom Constraint-Löser übernommen. Für <a href="Eugene_Freuder" title="Eugene Freuder">Eugene Freuder</a> stellt das Paradigma deshalb die bisher größte Annäherung an den „Heiligen Gral“ der Programmierung dar: Der Nutzer statuiert das Problem, der Computer löst es.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Constraints">Constraints</h2></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Constraint" title="Constraint">Constraint</a></div>

Der Begriff <a href="Constraint" title="Constraint">Constraint</a> bedeutet in etwa Zwang oder Nebenbedingung. Es handelt sich um spezielle <a href="Pr%C3%A4dikatenlogik" title="Prädikatenlogik">prädikatenlogische Formeln</a>, die Bedingungen oder Einschränkungen beschreiben. Im mathematischen Sinn sind damit auch <a href="Nebenbedingung" title="Nebenbedingung">Nebenbedingungen</a> gemeint, wie sie beispielsweise bei der Lösung mathematischer <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">Optimierungsprobleme</a> Anwendung finden.

Man kann zum Beispiel die Umrechnungsformel von <a href="Grad_Celsius" title="Grad Celsius">Grad Celsius</a> in <a href="Grad_Fahrenheit" title="Grad Fahrenheit">Grad Fahrenheit</a> als ein Constraint auffassen: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F=1{,}8\times C+32}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F=1{,}8\times C+32}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b26076d8c6a28ee4edd9b44c6f3f0a00529ea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.583ex; height:2.509ex;" alt="{\displaystyle F=1{,}8\times C+32}" loading="lazy">. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F=68}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F=68}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc733d330adb57be59007d429877313cb980afbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.164ex; height:2.176ex;" alt="{\displaystyle F=68}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=20}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=20}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ee79782d5dae34afae85f45d8557a03ba45f4b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.19ex; height:2.176ex;" alt="{\displaystyle C=20}" loading="lazy"> erfüllt, während <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99cf4e93252b52e6e3e47db8f3c6888b067613f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.002ex; height:2.176ex;" alt="{\displaystyle F=1}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/605a443c472808db9a502a801b8a2dfa5ee15d08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.027ex; height:2.176ex;" alt="{\displaystyle C=1}" loading="lazy"> das Constraint offensichtlich verletzt.

Das Constraint <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X^{2}\geq 0\land X\in \mathbb {R} }">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X^{2}\geq 0\land X\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c04bec2afa39edc47eb2afc2d663fb2bc5e0131.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.393ex; height:2.843ex;" alt="{\displaystyle X^{2}\geq 0\land X\in \mathbb {R} }" loading="lazy"> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X^{2}<0\land X\in \mathbb {R} }">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X^{2}<0\land X\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61e5cac29fd19c231147985c5402d2c9a8528f81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:16.393ex; height:2.676ex;" alt="{\displaystyle X^{2}<0\land X\in \mathbb {R} }" loading="lazy"> dagegen nie.<a href="#cite_note-2">[2]</a>

Ein weiteres Beispiel ist ein <a href="Pythagoreisches_Tripel" title="Pythagoreisches Tripel">pythagoreisches Tripel</a>, das von drei natürlichen Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem <a href="Definitionsbereich" class="mw-redirect" title="Definitionsbereich">Definitionsbereich</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,\dots ,100\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1,\dots ,100\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cb68f724313db03e688f2eee10541acddb71b747.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.153ex; height:2.843ex;" alt="{\displaystyle \{1,\dots ,100\}}" loading="lazy"> kann durch folgende Constraint-Konjunktion dargestellt werden:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}+y^{2}=z^{2}\land x,y,z\in \{1,\dots ,100\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f32a1f0c2be53e4f7c8ae020d249d1ae48ddfabb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.899ex; height:3.176ex;" alt="{\displaystyle x^{2}+y^{2}=z^{2}\land x,y,z\in \{1,\dots ,100\}}" loading="lazy"></dd></dl>

Eine mögliche Lösung ist das Tripel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y,z)=(3,4,5)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y,z)=(3,4,5)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b77e4112d6a227a494cede9461c7440c7b5cdca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.913ex; height:2.843ex;" alt="{\displaystyle (x,y,z)=(3,4,5)}" loading="lazy">.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Erfüllbarkeit_und_Lösungen">Erfüllbarkeit und Lösungen</h2></div>

Nachdem man ein Problem durch Constraints beschrieben hat, möchte man herausfinden, ob die Constraints erfüllbar sind. Zusätzlich können mögliche Lösungen von Interesse sein. Die Fragen nach der Erfüllbarkeit von Constraints und nach konkreten Lösungen sind eng miteinander verbunden. Ist ein Constraint erfüllbar, so gibt es mindestens eine Lösung. Allerdings gestaltet sich die Berechnung einer Lösung oft komplizierter als die Feststellung der Erfüllbarkeit.<a href="#cite_note-4">[4]</a>

Eine „naive“ Herangehensweise zur Entscheidung der Erfüllbarkeit und zur Berechnung konkreter Lösungen wäre, alle möglichen Belegungen der Variablen mit Werten durchzuprobieren. Allerdings ist die Anzahl möglicher Belegungen oft sehr groß oder unendlich, sodass diese Vorgehensweise scheitert. Deshalb kommen in vielen Situationen spezielle <a href="Algorithmus" title="Algorithmus">Algorithmen</a> zur Behandlung von Constraints zum Einsatz.

Constraint-Löser sind Algorithmen, die Tests und Operationen auf Constraints zur Verfügung stellen. Diese können häufig nicht nur die Erfüllbarkeit prüfen und konkrete Lösungen berechnen, sondern auch weitere Operationen auf Constraints durchführen.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Constraint-Systeme">Constraint-Systeme</h2></div>

Aus formaler Sicht stellen Constraints spezielle prädikatenlogische Formeln dar, mit deren Hilfe man Eigenschaften von Problemen und deren Lösung beschreibt.<a href="#cite_note-6">[6]</a> Dazu gehören Gleichungen und Ungleichungen über Zahlen, aber auch andere Ausdrücke über Zahlen, <a href="Boolesche_Algebra" title="Boolesche Algebra">boolesche Werte</a> oder beliebige andere Mengen wie Buchstaben oder Wörter.

Constraint-Löser funktionieren in der Regel nur auf einer speziellen Klasse von Constraints. Diese werden durch Constraint-Systeme klassifiziert. Dadurch lassen sich den Constraint-Systemen passende Lösungsmechanismen zuordnen.<a href="#cite_note-7">[7]</a>

Typische Constraint-Systeme sind:

<ul><li><a href="Lineares_Gleichungssystem" title="Lineares Gleichungssystem">Lineare Gleichungssysteme</a>: eine Menge <a href="Lineare_Gleichung" title="Lineare Gleichung">linearer Gleichungen</a> mit einer oder mehreren <a href="Variable_(Mathematik)" title="Variable (Mathematik)">Unbekannten</a>, die alle gleichzeitig erfüllt sein sollen. Um ein Gleichungssystem zu lösen, kann auf eine Vielzahl von Lösungsverfahren zurückgegriffen werden, z. B. das <a href="Gau%C3%9Fsches_Eliminationsverfahren" title="Gaußsches Eliminationsverfahren">gaußsche Eliminationsverfahren</a>.</li></ul>

<ul><li><a href="Lineare_Optimierung" title="Lineare Optimierung">Lineare Optimierung</a>: die <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">Optimierung</a> <a href="Lineare_Abbildung" title="Lineare Abbildung">linearer Zielfunktionen</a> über einer Menge, die durch lineare <a href="Gleichung" title="Gleichung">Gleichungen</a> und <a href="Ungleichung" title="Ungleichung">Ungleichungen</a> eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das <a href="Simplex-Verfahren" title="Simplex-Verfahren">Simplex-Verfahren</a>.</li></ul>

<ul><li><a href="Boolesche_Variable" class="mw-redirect" title="Boolesche Variable">Boolesche Constraints</a>: Boolesche Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als <a href="Aussagenlogik" title="Aussagenlogik">aussagenlogische</a> Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein Boolescher Constraint-Löser logische Operationen wie <a href="Negation" title="Negation">Negation</a>, <a href="Konjunktion_(Logik)" title="Konjunktion (Logik)">Konjunktion</a>, <a href="Disjunktion" title="Disjunktion">Disjunktion</a>, <a href="Implikation" title="Implikation">Implikation</a> und <a href="Logische_%C3%84quivalenz" title="Logische Äquivalenz">Äquivalenz</a>.<a href="#cite_note-8">[8]</a></li></ul>

<ul><li>Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. finite domains) zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung <a href="Kombinatorik" title="Kombinatorik">kombinatorischer</a> Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<a href="#cite_note-9">[9]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Constraint-basierte_Programmierung">Constraint-basierte Programmierung</h2></div>

Die Constraint-basierte Programmierung erlaubt die Integration von Constraints und ihren Lösungsmechanismen in eine Programmiersprache. Darüber hinaus ermöglicht sie in der Regel die Definition neuer Constraints. Constraint-<a href="Programmbibliothek" title="Programmbibliothek">Bibliotheken</a> erlauben die funktionale und syntaktische Erweiterung einer existierenden Sprache um Constraints unter Ausnutzung existierender Sprachkonzepte. Eine Constraint-basierte Sprache ist eine <a href="Semantik" title="Semantik">semantische</a> Erweiterung einer existierenden Sprache um neue Konzepte und Auswertungsmechanismen bis hin zu einem vollständigen Neuentwurf.<a href="#cite_note-10">[10]</a>

Ursprünglich entwickelte sich die Constraint-basierte Programmierung als Erweiterung der <a href="Logische_Programmierung" title="Logische Programmierung">logischen Programmierung</a>. Mittlerweile ist sie ein eigenständiger Bereich der <a href="K%C3%BCnstliche_Intelligenz" title="Künstliche Intelligenz">künstlichen Intelligenz</a> und hat vielfältige Anwendungsgebiete in Praxis und Wissenschaft.

<div class="mw-heading mw-heading3"><h3 id="Constraint-logische_Programmierung">Constraint-logische Programmierung</h3></div>

Die <a href="Logische_Programmierung" title="Logische Programmierung">logische Programmierung</a> arbeitet auf Basis einer <a href="Wissensdatenbank" title="Wissensdatenbank">Wissensdatenbank</a>, aus der die Lösung von Anfragen <a href="Deduktion" title="Deduktion">hergeleitet</a> wird. Bei der Auswertung von Anfragen werden die <a href="Pr%C3%A4dikat_(Logik)" title="Prädikat (Logik)">Prädikate</a> mit Hilfe der <a href="Resolution_(Logik)" title="Resolution (Logik)">Resolution</a> abgeleitet. Constraint-logische Programme unterscheiden sich von logischen Programmen nur insofern, als sie in den rechten Seiten der Klauseln und in Anfragen neben logischen Prädikaten auch Constraints zulassen, die mit Hilfe von Constraint-Lösern auf Erfüllbarkeit überprüft werden.<a href="#cite_note-11">[11]</a>

Die <a href="Syntax" title="Syntax">Syntax</a> Constraint-logischer Programme unterscheidet sich nicht wesentlich von logischen Programmen. Es sind lediglich auch Constraints in den rechten Seiten der Regeln und in den Anfragen zulässig. Während logische Prädikate weiterhin durch Unifikation behandelt werden, werden die zusätzlichen Constraints gesammelt, in den Constraint-Speicher übertragen und von einem Constraint-Löser behandelt. Constraint-logische Programme lassen oft verschiedene Constraint-Domänen (z. B. FD-Constraints, arithmetische Constraints oder boolesche Constraints) mit entsprechenden Lösungsverfahren zu, die dann beispielsweise in Form von Bibliotheken vorliegen.<a href="#cite_note-12">[12]</a>

Typische Constraint-logische Sprachen, die eine Generalisierung der logischen Sprachen darstellen, sind zum Beispiel ECLiPSe<a href="#cite_note-13">[13]</a>, CHIP<a href="#cite_note-14">[14]</a> und SICStus-Prolog<a href="#cite_note-15">[15]</a>.

<div class="mw-heading mw-heading3"><h3 id="Nebenläufige_Constraint-logische_Programmierung">Nebenläufige Constraint-logische Programmierung</h3></div>

Die nebenläufige Constraint-logische Programmierung (engl. Concurrent Constraint Logic Programming, CCLP) integriert das Konzept der <a href="Nebenl%C3%A4ufigkeit" title="Nebenläufigkeit">Nebenläufigkeit</a> in die Constraint-logische Programmierung. Nebenläufigkeit ist die Eigenschaft eines Systems, mehrere Berechnungen, <a href="Anweisung_(Programmierung)" title="Anweisung (Programmierung)">Anweisungen</a> oder <a href="Maschinenbefehl" class="mw-redirect" title="Maschinenbefehl">Befehle</a> gleichzeitig ausführen zu können. Das System verzichtet dadurch auf <a href="Sequentialisierung" title="Sequentialisierung">Sequentialisierung</a>. Dies ist dann möglich, wenn die betreffenden Aktionen voneinander kausal unabhängig sind, d. h. keine Aktion das Resultat einer anderen benötigt. Unabhängige Aktionen können entweder in beliebiger Reihenfolge sequentiell abgearbeitet werden oder echt <a href="Parallele_Programmierung" title="Parallele Programmierung">parallel</a> auf mehreren Rechnern gleichzeitig ausgeführt werden.

Das Modell der nebenläufigen Constraint-Programmierung kann auch mit partiellen Informationen über Variablenbelegungen arbeiten. Statt konkreter Daten für Variablen können auch Bedingungen auf diesen festgelegt werden.<a href="#cite_note-16">[16]</a>

Eine multiparadigmatische Programmiersprache, die unter anderem deklarative, parallele und Constraint-basierte Ansätze vereint, ist beispielsweise <a href="Oz_(Programmiersprache)" title="Oz (Programmiersprache)">Oz</a>.

<div class="mw-heading mw-heading3"><h3 id="Constraint-imperative_Programmierung">Constraint-imperative Programmierung</h3></div>

Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und <a href="Imperative_Programmierung" title="Imperative Programmierung">imperative Programmierung</a>. In imperativen Sprachen beschreibt der Programmierer, wie ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das Was, d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.<a href="#cite_note-17">[17]</a>

Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.<a href="#cite_note-18">[18]</a> Diese entstand als eine einfache imperative Basissprache und wurde zunächst um <a href="Funktionale_Programmierung" title="Funktionale Programmierung">funktionale Konzepte</a> wie <a href="Funktion_h%C3%B6herer_Ordnung" title="Funktion höherer Ordnung">Funktionen höherer Ordnung</a> erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichert<a href="#cite_note-19">[19]</a>:

<ul><li>Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.</li></ul>

<ul><li>Constraint-Anweisungen: Eine Constraint-Anweisung kann mehrere durch den and-Operator verknüpfte Constraints enthalten. Mit Ausführung der require-Anweisung werden die Constraints zum Constraint-Speicher des Constraint-Lösers hinzugefügt. Der Löser prüft die Erfüllbarkeit der Constraint-Konjunktionen und weist eine Lösung den Constraint-Variablen zu.</li></ul>

<ul><li>Nutzer-definierte Constraints: Diese abstrahieren von Constraints wie Funktionen von Ausdrücken. Sie dienen der Definition häufig auftretender Muster, um den Programmieraufwand zu verringern und die Lesbarkeit der Programme zu verbessern.</li></ul>

<ul><li>Constraint-Löser: Diese sind dafür verantwortlich, die mit require ausgeführten Constraints zu verwalten und Lösungen zu berechnen. Sind die Constraints im Speicher zusammen unerfüllbar, wird eine Exception ausgelöst.</li></ul>

Die <a href="C%2B%2B" title="C++">C++</a>-Bibliothek Turtle++ hat viele Konstrukte von Turtle übernommen und für eine harmonische Integration in C++ angepasst.

<div class="mw-heading mw-heading3"><h3 id="Constraint-objektorientierte_Programmierung">Constraint-objektorientierte Programmierung</h3></div>

Die Einbettung von Constraints in <a href="Objektorientierte_Programmierung" title="Objektorientierte Programmierung">objektorientierte Programmiersprachen</a> wird als Constraint-objektorientierte Programmierung bezeichnet.

Für die objektorientierte Programmiersprache <a href="Java_(Programmiersprache)" title="Java (Programmiersprache)">Java</a> existiert die Bibliothek firstcs zur objektorientierten Constraintprogrammierung. Ihr Kern bildet eine Klasse namens CS (Constraint-Solver). Jedes Objekt dieser Klasse besitzt und verwaltet Variablen über endlichen, ganzzahligen Domänen und Constraints über diesen Variablen. Aufgrund des objektorientierten Designs der Bibliothek ist es möglich, in einem Programm mehrere Constraint-Systeme gleichzeitig zu generieren und zu manipulieren, die jedoch gegenwärtig nur voneinander unabhängige CSP repräsentieren können. Des Weiteren gibt es die Klassen Domain, Variable, Constraint und die Unterklassen von Constraint, die um den Kern herum die grundlegenden Methoden und Verfahren zur Modellierung und Lösung von CSP bereitstellen.<a href="#cite_note-20">[20]</a>

Als ein weiterer Ansatz entstand die Programmiersprache Kaleidoscope, die Constraints in einen imperativen objektorientierten Stil integriert. Es ist eine der ersten Sprachen, bei der Constraints zwischen Attributen verschiedener Objekte spezifiziert werden.<a href="#cite_note-21">[21]</a>

Des Weiteren ist Koalog eine bekannte Java-Bibliothek für Finite-Domain-Constraints und Ilog-Solver eine C++-Bibliothek für verschiedene Domänen.

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung <a href="Nat%C3%BCrliche_Sprache" title="Natürliche Sprache">natürlicher Sprache</a>, im <a href="Maschinengest%C3%BCtztes_Beweisen" title="Maschinengestütztes Beweisen">maschinengestützten Beweisen</a>, in der Analyse von Programmen und in der <a href="Molekularbiologie" title="Molekularbiologie">Molekularbiologie</a> Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und <a href="Scheduling" title="Scheduling">Scheduling</a>-Aufgaben, <a href="Integrierter_Schaltkreis" title="Integrierter Schaltkreis">Schaltkreis</a>-Design und -Verifikation, graphische Systeme und <a href="Benutzerschnittstelle" title="Benutzerschnittstelle">Benutzerschnittstellen</a>.<a href="#cite_note-22">[22]</a>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Frédéric Benhamou, Narendra Jussien, Barry O’Sullivan: Trends in constraint programming. John Wiley and Sons: London/Newport Beach, 2007.</li>

<li>Thom Frühwirth, Slim Abdennadher: Constraint-Programmierung: Grundlagen und Anwendungen. Springer-Verlag: Berlin/Heidelberg, 1997, ISBN 3-540-60670-X</li>

<li>Petra Hofstedt, Armin Wolf: Einführung in die Constraint-Programmierung. (Springer eXamen-press) Springer-Verlag: Berlin/Heidelberg, 2007, ISBN 978-3-540-23184-4</li>

<li>Francesca Rossi, Peter van Beek, Toby Walsh (Hrsg.): Handbook of Constraint Programming. Elsevier: Amsterdam et al., 2006.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.a4cp.org/">Association for Constraint Programming</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Eugene C. Freuder: In Pursuit of the Holy Grail. In: Constraints 2 (1), 1997, S. 57–61; Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 51–52.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 205.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 58.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 60.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Für eine formale Definition von Constraints siehe Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 54–55.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 53–55.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 177.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 57, 71.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 220.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 127–133.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 221.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">↑</a> <a rel="nofollow" class="external text" href="http://eclipseclp.org/index.html">The ECLiPSe Constraint Programming System</a>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">↑</a> Coystec: <a rel="nofollow" class="external text" href="http://www.cosytec.com/production_scheduling/chip/chip_technology.htm">CHIP V5</a>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">↑</a> SICStus: <a rel="nofollow" class="external text" href="https://sicstus.sics.se/">SICStus Prolog</a>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 141–162.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">↑</a> catamorph.de: <style data-mw-deduplicate="TemplateStyles:r261891140">

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160408134625/http://catamorph.de/turtle/turtle.de.html">Turtle – eine constraint-imperative Programmiersprache</a> (<a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a> vom 8. April 2016 im <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>)

</li>

<li id="cite_note-19"><a href="#cite_ref-19">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185–192.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">↑</a> Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 199–215.

</li>

<li id="cite_note-21"><a href="#cite_ref-21">↑</a> Gus Lopez, Bjorn Freeman-Benson, Alan Borning: Kaleidoscope: A Constraint Imperative Programming Language. In: Brian Mayoh, Enn Tyugu, Jaan Penjam: Constraint Programming. Springer-Verlag, S. 313–329.

</li>

<li id="cite_note-22"><a href="#cite_ref-22">↑</a> Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.

</li>

</ol>

</div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-02-21" href="https://de.wikipedia.org/wiki/?title=Constraintprogrammierung&oldid=253549582">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>